1. Field of the Invention
The present invention relates to a method, system, and program for implementing priority inheritance in an operating system to avoid priority inversion problems.
2. Description of the Related Art
The prior art Portable Operating System Interface (POSIX) standards define an interface between application programs and operating systems. Systems that utilize the POSIX standards include the prior art International Business Machines Corporation (“IBM”) AIX operating system, most UNIX operating systems, Microsoft Corporation's WINDOWS® NT operating system, IBM's OS/2® operating system, and JAVA® systems. AIX and OS/2 are registered trademarks of IBM; UNIX is a registered trademark of the Open Group; WINDOWS is a registered trademark of Microsoft Corporation; and JAVA is a trademark of Sun Microsystems, Inc. In prior art POSIX compliant systems, a thread is an independent flow of control that operates within the same address space as other independent flows of controls. Multiple threads may be grouped into a single entity called a process. In a multiprocessor system, multiple threads can execute at the same time, one on each processor. There may be multiple processes executing, each including multiple threads.
A process provides a common address space and common system resources, including file descriptors, signal actions, shared libraries, and inter-process communication tools (such as message queues, pipes, semaphores, or shared memory). The thread is the schedulable entity. It has only those properties that are required to ensure its independent flow of control.
Processes and threads are managed by a kernel program. The kernel includes operating system primitives and contains programs for such tasks as input/output, management and control of hardware, the scheduling of user tasks, and frequently needed functions of the Base Operating System.
A user thread is an entity used by programmers to handle multiple flows of controls within a program. The API for handling user threads is provided by a library, the threads library. In the prior art IBM AIX operating system, and certain other operating systems, a user thread only exists within a process; a user thread in process A cannot reference a user thread in process B. The library uses a proprietary interface to handle kernel threads for executing user threads. The user threads API, unlike the kernel threads interface, is part of a portable programming model. Thus, a multi-threaded program developed on an AIX system can easily be ported to other systems.
A mutex is a mutual exclusion lock. To insure that two threads do not concurrently access the same shared resource, one thread holds the mutex lock, which prevents other threads from accessing the resource governed by the mutex. To access a memory area, a thread first accesses and locks the mutex, performs the read/write operation with respect to the shared resource, and then unlocks the mutex to allow other threads to access the resource. Threads are ranked according to a priority attribute. Higher priority threads have preferred access to CPU time over lower priority threads.
The situation of priority inversion occurs when a thread is holding a mutex and a higher priority thread attempts to access the resource governed by the mutex. In such case, the higher priority thread must wait for the lower priority thread to release the mutex. Because the higher priority thread must wait for the thread executing at the lower priority to release the mutex, the higher priority thread is effectively reduced to the lower priority while the lower priority thread holds the mutex.
Unbounded priority refers to a priority inversion situation where a medium priority thread is given priority to the processor cycles and prevents the low priority thread holding the mutex from completing its process and releasing the mutex to the high priority thread. In such case the high priority thread may be blocked indefinitely from obtaining the mutex by the medium priority thread, or at least until the medium access thread completes using the processor and allows the low priority thread to complete processing and release the mutex.
Two common solutions to priority inversion include priority inheritance and priority ceiling. With priority inheritance, the lower priority thread holding the mutex has its priority adjusted to the higher priority of the thread wanting access. When the lower priority thread executing at the higher priority releases the mutex, its priority is then restored to the lower priority. With the priority ceiling method, when a thread acquires a mutex, its priority is increased to a priority higher than any other thread that may acquire the mutex.
Although priority inheritance may appear straightforward in theory, it is often difficult to implement. For instance, in the prior art IBM AIX system and other operating systems, priority inheritance cannot be implemented between threads executing within different processes because a thread in one process cannot affect the priority of a thread in another process. Such systems can implement the priority ceiling method, because a given thread may adjust its own priority to the higher ceiling priority. However, the priority ceiling technique is sometimes inefficient because it may boost the priority of a thread accessing a mutex to an unnecessarily high priority, especially if other threads that subsequently want the mutex are at a priority that is lower than the thread currently accessing the mutex. This unnecessary boosting of threads can slow down overall system processing by providing more CPU cycles than needed to threads holding the mutex. In this respect, priority inheritance is preferred because it will not boost the priority of the thread currently holding the mutex higher than necessary to prevent priority inversion.
There is thus a need in the art to provide a method for implementing priority inheritance in operating systems. Further, there is a need in the art to provide priority inheritance for operating systems that do not allow threads to affect priority between processes.